//bf 和 sp算法解决最短路问题

#include <iostream>
#include <vector>
using namespace std;

//const int N = 1e4 + 10;
//typedef pair<int, int> PII;
//const int err = 2147483647;
//
//int arr[N];			//存储最终结果
//vector<PII> dp[N];	//邻接表

//int main()
//{
//	ios::sync_with_stdio(false);
//	int n, m, s; cin >> n >> m >> s;
//	for (int i = 1; i <= m; i++)
//	{
//		int u, v, w; cin >> u >> v >> w;
//		//存边
//		dp[u].push_back(make_pair(v, w));
//	}
//
//	//初始化arr
//	for (int i = 0; i <= n; i++)
//	{
//		arr[i] = err;
//	}
//	arr[s] = 0;
//
//	//对所有节点进行 n - 1次松弛操作
//	for (int i = 1; i < n; i++)
//	{
//		bool flag = false;
//		for (int j = 1; j <= n; j++)
//		{
//			if (arr[j] == err) continue;
//			for (const auto& e : dp[j])
//			{
//				int v = e.first; int w = e.second;	
//				if (arr[j] + w < arr[v])
//				{
//					arr[v] = arr[j] + w;
//					flag = true;
//				}
//			}
//		}
//		if (!flag) break;
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		cout << arr[i] << " ";
//	}
//
//	return 0;
//}

//队列优化版
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 1e4 + 10;
typedef pair<int, int> PII;
const int err = 2147483647;

int arr[N];			//存储最终结果
vector<PII> dp[N];	//邻接表
bool check[N];

int main()
{
	ios::sync_with_stdio(false);
	int n, m, s; cin >> n >> m >> s;
	for (int i = 1; i <= m; i++)
	{
		int u, v, w; cin >> u >> v >> w;
		//存边
		dp[u].push_back(make_pair(v, w));
	}

	queue<int> que;

	//初始化arr
	for (int i = 0; i <= n; i++)
	{
		arr[i] = err;
	}


	arr[s] = 0;
	que.push(s);
	check[s] = true;

	while (que.size())
	{
		int u = que.front(); que.pop(); check[u] = false;
		//对这个节点进行松弛操作
		for (const auto& e : dp[u])
		{
			int v = e.first; int w = e.second;
			if (arr[u] + w < arr[v])
			{
				arr[v] = arr[u] + w;
				if (!check[v])
				{
					check[v] = true; que.push(v);
				}
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		cout << arr[i] << " ";
	}

	return 0;
}